package com.hardy.data_structure;

/**
 * Author: Hardy
 * Date:   2019/3/21
 * Description:
 **/
public class DoubleLinked extends Linked {
    public void add(int val) {
        Node node = new Node(val);

        if (root == null) {
            root = node;
            length++;
            return;
        }

        Node pre = this.root;
        while (pre.next != null) {
            pre = pre.next;
        }

        pre.next = node;
        node.pre = pre;
        length++;
    }

    public void del(int val) {
        if (root == null) return;

        Node node = this.root;
        while (node != null && node.val != val) {
            node = node.next;
        }

        if (node == null) return;

        Node pre = node.pre;
        Node next = node.next;

        if (pre != null)
            pre.next = next;
        else
            root = next;

        if (next != null) next.pre = pre;
        length--;
    }

    public void insert(int idx, int val) {
        if (idx < 0 || idx > length) {
            System.out.println("位置不合法");
            return;
        }

        Node node = new Node(val);

        if (root == null) {
            root = node;
            length++;
            return;
        }

        Node pre = null;
        Node next = root;
        for (int i = 0; i < idx; i++) {
            pre = next;
            next = next.next;
        }

        node.pre = pre;
        node.next = next;

        if (pre == null)
            root = node;
        else
            pre.next = node;

        if (next != null) next.pre = node;
        length++;
    }

    public void remove(int idx) {
        if (idx < 0 || idx >= length) {
            System.out.println("位置不合法");
            return;
        }

        Node node = root;
        for (int i = 0; i < idx; i++) {
            node = node.next;
        }

        Node pre = node.pre;
        Node next = node.next;

        if (pre != null)
            pre.next = next;
        else
            root = next;

        if (next != null) next.pre = pre;

        length--;
    }

    public void reverse() {
        if (root == null) return;

        Node node = root;
        while (node != null) {
            Node next = node.next;

            // 反转
            node.next = node.pre;
            node.pre = next;

            // 重新指根
            root = node;

            // 偏移
            node = next;
        }
    }
}
